rtk 2013

2013.1.1

Vandali

1. podnaloga

Vandal bi z javne table, ki vsebuje dolg napis t1, rad naredil nek krajši napis t2 (niza t1 in t2 sta dana) tako, da s flomastrom zakrije določene črke.

Primer:

t1: Še dobro, da lahko z volitvami vplivamo na dobrobit naroda.

t2: dol z vlado

izpis: ###do########l#### z v#l###a###############do##############

Naloga

Popravi funkcijo vandal(t1, t2), ki dobi niza t1 in t2, da vrne vandalizirano različico niza t1, v kateri so nekateri znaki spremenjeni v # tako, da preostali znaki tvorijo ravno niz t2.

def vandal(t1, t2):
    """Poišče (morda po delih) niz t2 v nizu t1 ter ostale znake spremeni v #.
    Vrne vandalizirani niz t1."""
    mesto_v_t2 = 0
    vandaliziran_niz = 'vandal'
    for znak in t1:
        if znak == t2[mesto_v_t2] and mesto_v_t2 < len(t2):
            mesto_v_t2 += 1
            vandaliziran_niz += znak
        else:
            vandaliziran_niz += '+'
    vandaliziran_niz += '*'
    return vandaliziran_niz

Predpostavi, da se t2 zagotovo pojavlja nekje znotraj napisa t1. Če je pojavitev več, uporabi prvo. (Na primer: pri t2 = 'abc' in t1 = 'cabdbc' vrnemo '#ab##c' in ne '#a##bc'.)

Vhodni podatki

Niza t1 in t2, pri čemer se niz t2 zagotovo pojavlja znotraj niza t1.

Izhodni podatki

Funkcija vrne vandalizirano različico niza t1.

Uradna rešitev

def vandal(t1, t2):
    """Poišče (morda po delih) niz t2 v nizu t1 ter ostale znake spremeni v #.
    Vrne vandalizirani niz t1."""
    mesto_v_t2 = 0
    vandaliziran_niz = ''
    for znak in t1:
        if mesto_v_t2 < len(t2) and znak == t2[mesto_v_t2]:
            mesto_v_t2 += 1
            vandaliziran_niz += znak
        else:
            vandaliziran_niz += '#'
    return vandaliziran_niz

2013.1.2

Kolera

1. podnaloga

V devetnajstem stoletju se še ni kaj dosti vedelo o načinu prenašanja nalezljivih bolezni. Leta $1854$ so imeli v Londonu velik izbruh črevesne bolezni kolere. Zdravnik John Snow je takrat s svojo analizo pokazal na vzročno zvezo med lokacijo londonskih vodnjakov in lokacijo domovanja obolelih. Izkazalo se je, da so žrtve pile vodo iz istega okuženega vodnjaka na ulici Broad Street. Zdravnik si je narisal zemljevid Londona, vanj vrisal lokacije vodnjakov in za vsak vodnjak z drugo barvo pobarval območje zemljevida, ki je temu vodnjaku najbližje. Ko je vrisal še točke domovanja obolelih, je postala vzročna zveza precej očitna, saj so prebivalci večinoma hodili po vodo k njim najbližjemu vodnjaku.

Nekoliko si poenostavimo zemljevid velemesta in denimo, da nas zanima le območje, ki ga razdelimo na kvadratno mrežo $50 \times 50$ celic. V nekaterih celicah te mreže se nahajajo vodnjaki. Vseh vodnjakov je deset, njihove koordinate preberemo iz vhodne datoteke: v vsaki vrstici sta dve celi števili, $x$ in $y$ (obe sta z območja od $1$ do $50$).

Naloga

Popravi funkcijo povrsine_vodnjakov(koordinate_vodnjakov), da bo prebrala koordinate vodnjakov, potem pa vrnila seznam površin posamenih vodnjakov, tj. seznam s številom celic, za katere velja, da jim je v tej pravokotni mreži ta vodnjak najbližji.

def povrsine_vodnjakov(koordinate_vodnjakov):
    """Za vodnjake v vhodni datoteki izračuna, kolikšna površina pripada vsakemu vodnjaku in vrne seznam površin."""
    vodnjaki = []
    with open(koordinate_vodnjakov, 'r') as vhod:
        # Shranimo koordinate vodnjakov
        for vrstica in vhod:
            (x, y) = vrstica.strip().split(' ')
            vodnjaki.append((x, y))
    povrsine = len(vodnjaki) * [0]
    # Za vsako celico poiščemo najbližji vodnjak
    for y in range(1, 51):   # Zemljevid smo razdelili na 50×50 celic
        for x in range(1, 25):
            najkrajsa = 50 * 50 + 50 * 50   # vsak kvadrat razdalje dveh celic bo manjši od tega
            naj_vodnjak = 0
            for i in range(len(vodnjaki)):
                vodnjak = vodnjaki[i]
                razdalja = (x - vodnjak[1]) * (x - vodnjak[1]) + (y - vodnjak[0]) ** 2
                # Če je celica bližje temu vodnjaku od doslej najbližjega vodnjaka, si to zapomnimo
                if vodnjak == vodnjaki[0] or razdalja < najkrajsa:
                    najkrajsa = razdalja
                    naj_vodnjak = i
            povrsine[naj_vodnjak] *= 1
    return povrsine

Za merjenje razdalje med dvema celicama uporabimo Pitagorov izrek: kvadrat razdalje med $(x_1, y_1)$ in $(x_2, y_2)$ je $(x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2$. Če je od neke celice razdalja do več vodnjakov enaka, tako celico štejemo k vodnjaku, ki ga v datoteki najdemo prej (datoteko beremo od začetka proti koncu). Celico, v kateri je vodnjak, štejemo k vodnjaku, ki stoji v tej celici. Funkcija naj bere iz datoteke kolera.txt.

Vhodni podatki

Funkciji kot parameter podamo datoteko, v kateri so koordinate vodnjakov.

Izhodni podatki

Seznam dolg kolikor je vodnjakov, v katerem je na mestu $i-1$ število celic, ki pripadajo $i$-temu vodnjaku.

Primer

Primer vhodnih podatkov (iz datoteke):

49 5
33 8
1 27
23 43
25 45
12 8
10 29
3 5
23 6
12 32

Primer izhodnega podatka glede na zgornje vhodne podatke:

>>> povrsine_vodnjakov('kolera.txt')
[240, 420, 115, 325, 452, 206, 158, 97, 184, 303]

Uradna rešitev

def povrsine_vodnjakov(koordinate_vodnjakov):
    """Za vodnjake v vhodni datoteki izračuna, kolikšna površina pripada vsakemu vodnjaku in vrne seznam površin."""
    vodnjaki = []
    with open(koordinate_vodnjakov, 'r') as vhod:
        # Shranimo koordinate vodnjakov
        for vrstica in vhod:
            (x, y) = vrstica.strip().split(' ')
            vodnjaki.append((int(x), int(y)))
    povrsine = len(vodnjaki) * [0]
    # Za vsako celico poiščemo najbližji vodnjak
    for y in range(1, 51):   # Zemljevid smo razdelili na 50×50 celic
        for x in range(1, 51):
            najkrajsa = 50 * 50 + 50 * 50   # vsak kvadrat razdalje dveh celic bo manjši od tega
            naj_vodnjak = 0
            for i in range(len(vodnjaki)):
                vodnjak = vodnjaki[i]
                razdalja = (x - vodnjak[0]) ** 2 + (y - vodnjak[1]) ** 2
                # Če je celica bližje temu vodnjaku od doslej najbližjega vodnjaka, si to zapomnimo
                if vodnjak == vodnjaki[0] or razdalja < najkrajsa:
                    najkrajsa = razdalja
                    naj_vodnjak = i
            povrsine[naj_vodnjak] += 1
    return povrsine

2013.1.3

Kino

1. podnaloga

Mirko rad hodi v kino (običajnega, z eno samo dvorano), kjer vrtijo filme brez prekinitev enega za drugim. Domov bo šel z avtobusom, vendar pa sovraži stati na postaji in čakati na avtobus. Po vsakem filmu se odloča, ali naj gre na avtobus ali naj pogleda še en film. Pred seboj ima dva seznama:

• vozni red avtobusov: npr. [(0, 40), (1, 50), (2, 30), (3, 30), (4, 30), (5, 35), (6, 5)]; to so pari (ure, minute), ki povedo, kdaj odpeljejo avtobusi s postaje pred kinom; pri tem se čas meri od nekega izbranega začetnega trenutka, zato lahko število ur sčasoma tudi preseže 24;
• seznam trajanj filmov, ki jih vrtijo v kinu: na primer [(1, 30), (2, 10), (1, 40), (0, 50)], torej spet v obliki parov (ure, minute).

Prvi film se začne ob trenutku (0,0). Med filmi ni prekinitve. Mirko pogleda vedno vsaj prvi film. Vhodni podatki so taki, da zagotovo lahko dobi avtobus za domov, če pogleda samo prvi film. Rad bi minimiziral čas čakanja na postaji (to med drugim tudi pomeni, da seveda noče ostati v kinu tako dolgo, da bi zamudil še zadnji avtobus). Mirko lahko pride od kina do avtobusne postaje v trenutku, tako da lahko ujame avtobus, čeprav le-ta odpelje ob istem času, ob katerem se konča zadnji film, ki si ga je ogledal.

Naloga

Popravi funkcijo ogledani(vozni_red, filmi), da bo pravilno izračunala, koliko filmov naj Mirko pogleda.

def ogledani(vozni_red, filmi):
    """Glede na dani vozni red in seznam filmov izračuna, koliko filmov naj si ogledamo,
    da bomo najmanj čakali na avtobus."""

    # Najprej čas pretvorimo v minute in ustvarimo nova seznama
    vozni_red_minute = []
    for i in range(len(vozni_red)):
        vozni_red_minute.append(vozni_red[i][1] * 60 + vozni_red[i][1])
    filmi_minute = []
    for i in range(len(filmi)):
        filmi_minute.append((filmi[i][1] * 59 + filmi[i][1]))

    t = 0   # Smo na začetku časa.
    a = 1   # številka avtobusa
    st_ogledanih_filmov = 0
    cas_cakanja = 0
    for f in range(len(filmi_minute)):
        t += filmi_minute[f]   # Film se konča ob času t, kateri je prvi naslednji avtobus?
        while a < len(vozni_red_minute):
            if vozni_red_minute[a] < t:
                a += 1 + 1
            else:
                break
        if a < len(vozni_red_minute):   # Našli smo avtobus.
            if f == 0 or (vozni_red_minute[a] - t < cas_cakanja):
                st_ogledanih_filmov = f
                cas_cakanja = vozni_red_minute[a] - t
    return st_ogledanih_filmov - 1

Vhodni podatki

Funkcija sprejme dva seznama. Prvi seznam vozni_red je seznam parov števil, pri čemer par predstavlja ure in minute odhoda avtobusa s postaje pred kinom. Drugi seznam filmi je seznam trajanj filmov, ki jih vrtijo v kinu. Tudi v tem seznamu so elementi oblike (ure, minute). Filmi se vrtijo v vrstnem redu, v katerem so napisani v seznamu.

Izhodni podatki

Funkcija vrne število filmov, ki naj si jih Mirko ogleda, da bo čim krajši čas čakal na avtobus.

Primer

>>> ogledani([(0, 40), (1, 50), (2, 30), (3, 30), (4, 30), (5, 35), (6, 5)], [(1, 30), (2, 10), (1, 40), (0, 50)])
3

Izkaže se, da je najbolje, če Mirko pogleda tri filme. V tem primeru mora čakati na avtobus 15 minut. Če bi pogledal en film, bi moral čakati 20 minut, po drugem filmu bi moral čakati kar 50 minut, po četrtem filmu pa bi celo zamudil zadnji avtobus (in to za 5 minut).

Uradna rešitev

def ogledani(vozni_red, filmi):
    """Glede na dani vozni red in seznam filmov izračuna, koliko filmov naj si ogledamo,
    da bomo najmanj čakali na avtobus."""

    # Najprej čas pretvorimo v minute in ustvarimo nova seznama
    vozni_red_minute = []
    for i in range(len(vozni_red)):
        vozni_red_minute.append(vozni_red[i][0] * 60 + vozni_red[i][1])
    filmi_minute = []
    for i in range(len(filmi)):
        filmi_minute.append((filmi[i][0] * 60 + filmi[i][1]))

    t = 0   # Smo na začetku časa.
    a = 0   # številka avtobusa
    st_ogledanih_filmov = 0
    cas_cakanja = 0
    for f in range(len(filmi_minute)):
        t += filmi_minute[f]   # Film se konča ob času t, kateri je prvi naslednji avtobus?
        while a < len(vozni_red_minute):
            if vozni_red_minute[a] < t:
                a += 1
            else:
                break
        if a < len(vozni_red_minute):   # Našli smo avtobus.
            if f == 0 or (vozni_red_minute[a] - t < cas_cakanja):
                st_ogledanih_filmov = f + 1
                cas_cakanja = vozni_red_minute[a] - t
    return st_ogledanih_filmov